package com.example.algorithm.base;

import org.junit.Test;

import java.text.SimpleDateFormat;
import java.time.*;
import java.time.temporal.ChronoUnit;
import java.util.*;

/**
 * description
 *
 * @author Mi Dakun
 * @version 2021-12-17
 */
public class BlueCup {

    // 平年12个月各月天数
    private static final int[] COMMON_MONTH_DAY = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    private static final int[] COMMON_LAST_DAY_INDEX = {30, 58, 89, 119, 150, 180, 211, 242, 272, 303, 333, 364};

    @Test
    public void test() {
        System.out.println(Integer.MAX_VALUE);
    }

    @Test
    public void guessAge() {
        // 猜年龄：年龄的3次方是4位数，4次方是6位数，且这十个数字刚好包含0-9并均只出现一次。
        // 遍历法：首先减小范围，10的3次方是1000，是最小的四位数，50的3次方是125000，已是6位数，则猜测范围：10~50
        long start = System.currentTimeMillis();
        for (int i = 10; i < 50; i++) {
            long cubicResult = i * i * i;
            long forthResult = cubicResult * i;
            if ((cubicResult > 999 && cubicResult < 10000) && (forthResult > 99999 && forthResult < 1000000)) {
                String concatResult = cubicResult + "" + forthResult;
                if (concatResult.contains("0") && concatResult.contains("1") && concatResult.contains("2")
                        && concatResult.contains("3") && concatResult.contains("4") && concatResult.contains("5")
                        && concatResult.contains("6") && concatResult.contains("7") && concatResult.contains("8")
                        && concatResult.contains("9")) {
                    System.out.println("true:" + i + ", concat:" + concatResult);
                    break;
                }
            }
        }
        System.out.println("totalTime=" + (System.currentTimeMillis() - start));
        // 总结1：不能使用Math.pow()，因为参数和输出是double，自带一位小数，需要额外剪切，应该使用乘法(*)直接运算
        // 总结2：计算立方和4次方后，直接转化为字符串然后判断位数，与使用数字比较大小来确定位数，在当前循环次数(40)下性能差不多。
    }

    @Test
    public void calcDays() {
        // 第几天：2000年的1月1日，是那一年的第1天。 那么，2000年的5月4日，是那一年的第几天？
        // 分析：直接心算(31+29+31+30+4)或者写代码
        // 写代码使用LocalDateTime.until,但要注意，它在中国的月份是从1开始的
        int fromYear = 2000;
        int fromMonth = 0; // 注意，Calendar中month起始为0
        int fromDay = 1;
        int toYear = 2000;
        int toMonth = 6;
        int toDay = 7;
        LocalDate from = LocalDate.of(fromYear, fromMonth + 1, fromDay);
        LocalDate to = LocalDate.of(toYear, toMonth + 1, toDay);
        long sampleDays = from.until(to, ChronoUnit.DAYS);
        System.out.println("sampleDays:" + sampleDays);
        int calcDays = getEpoDays(toYear, toMonth, toDay) - getEpoDays(fromYear, fromMonth, fromDay);
        System.out.println("calcDays:" + calcDays);
        System.out.println("equal:" + (sampleDays == calcDays));
    }

    @Test
    public void bigNumberCalc() {
        // 数字分块算法。以下算法将数字分成了两块。
        int[] r = new int[4];
//        int x = 12345678, y = 87654321;
        int x = 1000, y = 10000;
        int base = 10000;
        int baseLen = (base + "").length() - 1;
        int x2 = x / base;  // 单位：base
        int x1 = x % base;  // 单位：1
        int y2 = y / base;  // 单位：base
        int y1 = y % base;  // 单位：1

        int n1 = x1 * y1;  // 单位：1
        int n2 = x1 * y2;  // 单位：base
        int n3 = x2 * y1;  // 单位：base
        int n4 = x2 * y2;  // 单位：base^2

        r[3] = n1 % base;  // 单位：1
        r[2] = n1 / base + n2 % base + n3 % base;  // 单位：base
        r[1] = n2 / base + n3 / base + n4 % base; // 单位：base^2
        r[0] = n4 / base;  // base^3

        r[1] += r[2] / base;  // 进位：base之和进位base^2
        r[2] = r[2] % base;  // 若有进位，则取余，若无进位，则取原数
        r[0] += r[1] / base;  // 进位
        r[1] = r[1] % base;  // 取余或原数


        System.out.printf("%s%s%s%s", r[0], getRealNumberStr(r[1], baseLen),
                getRealNumberStr(r[2], baseLen), getRealNumberStr(r[3], baseLen));
    }

    @Test
    public void perfectSquareNumber() {
        // 完美平方数  [解法一：使用0,1,4,9拼接组合字符，计算时间太长]
        // 如果整个整数 X 本身是完全平方数，同时它的每一位数字也都是完全平方数，我们就称 X 是完美平方数。
        // 前几个完美平方数是 0、1、4、9、49、100、144……
        // 即第 1 个完美平方数是 0，第 2 个是 1，第 3 个是 4，……
        // 请你计算第 2020 个完美平方数是多少？
//        Pattern pattern = Pattern.compile("^[0149]+$");
        int count = 1; // 完美平方数计数
        String[] eleArray = {"0", "1", "4", "9"};  // 元素组
        List<Integer> current = new ArrayList<>();
        current.add(0);
        int rIndex = 0;
        System.out.println("count=" + count + ", number=" + getCurrentStr(current, eleArray));
        while (true) {
            rIndex = calcRIndex(current, rIndex);
            // 验证是否能被开平方
            String currentStr = getCurrentStr(current, eleArray);
            double sqrt = Math.sqrt(Long.parseLong(currentStr));
            if (sqrt == (long) sqrt) {
                count++;
                System.out.println("count=" + count + ", number=" + currentStr);
                if (count >= 2020) {
                    break;
                }
            }
        }
    }

    @Test
    public void perfectSquareNumber1() {
        // 完美平方数  [解法二：逆向思维：完美平方数的根都是整数...]
        int count = 1;
        String[] results = new String[2021];
        for (int i = 0; i < Integer.MAX_VALUE; i++) {
            // count=2021时i=13793803^2已溢出，本题得出的结果是溢出结果，不是真实结果
            String squared = i * i + "";
            boolean inExp = true;
            for (int j = 0; j < squared.length(); j++) {
                switch (squared.charAt(j)) {
                    case '0':
                    case '1':
                    case '4':
                    case '9':
                        break;
                    default:
                        inExp = false;
                        break;
                }
                if (!inExp) {
                    break;
                }
            }
            if (inExp) {
                System.out.printf("count=%s number=%s \n", count, squared);
                if (count < 2021) {
                    count++;
                } else {
                    break;
                }
            }
        }
    }

    @Test
    public void phalanxRotation() {
        // 方阵转置：顺时针90°再纵轴镜像
        int m = 3, n = 4;
        int[][] mn = new int[m][n];
        Random random = new Random();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mn[j][i] = random.nextInt(20);
            }
        }
        System.out.println("输入结束，您输入的方阵为：");
        System.out.printf("%s %s", m, n);
        for (int i = 0; i < m; i++) {
            System.out.println();
            for (int j = 0; j < n; j++) {
                System.out.printf("%s ", mn[i][j]);
            }
        }
        System.out.println();
        System.out.print("转换后的方阵为：");
        for (int i = 0; i < n; i++) {
            System.out.println();
            for (int j = 0; j < m; j++) {
                System.out.printf("%s ", mn[i][j]);
            }
        }
        // 总结：方阵转置其实比较形象，关键在于横纵变换，遍历方向变换，用统筹思维解决问题
    }

    @Test
    public void microbialProliferation() {
        // 微生物增殖
        // 假设有两种微生物 X 和 Y，X出生后每隔3分钟分裂一次（数目加倍），Y出生后每隔2分钟分裂一次（数目加倍）。
        // 一个新出生的X，半分钟之后吃掉1个Y，并且，从此开始，每隔1分钟吃1个Y。
        // 现在已知有新出生的 X=10, Y=89，求60分钟后Y的数目。如果X=10，Y=90  呢？
        long X = 10, Y = 90;  // 认为初始时间为0时，现存所有X和Y均为新生
        for (int i = 0; i < 61; i++) {  // 60分钟后，是完整的60个时间单位，因此是0~60
            // 首先考虑增殖，因增殖发生在每隔3分钟或2分钟的0秒，认为分裂是瞬间(耗时为0)完成
            if (i > 2 && i % 3 == 0) {
                X = 2 * X;
            }
            if (i > 1 && i % 2 == 0) {
                Y = 2 * Y;
            }
            // 其次考虑吞噬，因吞噬发生在每分钟的第30秒，也认为瞬间完成。
            if (i < 60) {  // 第60分钟0秒游戏结束，第60次吞噬还未开始
                Y = Y - X;  // 一个X吃掉一个Y
            }
        }
        System.out.printf("X=%s, Y=%s", X, Y);

    }

    @Test
    public void gradesCounts() {
        Random random = new Random();
        int n = random.nextInt(5) + 5;
        Student[] students = new Student[n];
        for (int i = 0; i < n; i++) {
            Student student = new Student();
            student.xm = "s" + (i + 1);
            student.xh = i + 1;
            student.yy = 30 + random.nextInt(699) / 10.0;
            student.sx = 30 + random.nextInt(699) / 10.0;
            student.cpp = 30 + random.nextInt(699) / 10.0;
            students[i] = student;
        }
        double sum = 0, min = 301, max = 0;  // 使用比较法获取最大最小值
        String mins = "", maxs = "";  // 最终最小、最大值所对应的学生姓名
        for (int i = 0; i < n; i++) {
            sum = students[i].yy + students[i].sx + students[i].cpp;
            if (sum > max) {
                max = sum;
                maxs = students[i].xm;
            }
            if (sum < min) {
                min = sum;
                mins = students[i].xm;
            }
        }
        System.out.printf("maxs=%s \n", maxs);
        System.out.printf("mins=%s \n", mins);
    }

    @Test
    public void galaxyBomb() {
        // 星系炸弹：实际上仍是变相计算日期
        // 在X星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。
        // 每个炸弹都可以设定多少天之后爆炸。比如：阿尔法炸弹2015年1月1日放置，定时为15天，则它在2015年1月16日爆炸。
        // 有一个贝塔炸弹，2014年11月9日放置，定时为1000天，请你计算它爆炸的准确日期。
        int fromYear = 2014;
        int fromMonth = Calendar.NOVEMBER;
        int fromDay = 9;
        int addDays = 1000;
        Calendar instance = Calendar.getInstance();
        instance.set(fromYear, fromMonth, fromDay);
        instance.add(Calendar.DATE, addDays);
        System.out.println(new SimpleDateFormat("yyyy-MM-dd").format(instance.getTime()));
        System.out.println(customAddDays(fromYear, fromMonth, fromDay, addDays));
    }

    @Test
    public void runningTrain() {
        // 跑步训练：实际还是循环
        // 小明要做一个跑步训练。初始时，小明充满体力，体力值计为 10000 。
        // 如果小明跑步，每分钟损耗 600的体力。如果小明休息，每分钟增加 300 的体力。体力的损耗和增加都是均匀变化的。
        // 小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。如果某个时刻小明的体力到达 0 ，他就停止锻炼。
        // 请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。
        // 每2分钟体力减少
        int total = 10000;
        int per2minDecr = 600 - 300;
        int base = total / per2minDecr;
        int rest = total % per2minDecr;
        while (rest < 300) {
            base--;
            rest += 300;
        }
        int sec = rest / (600 / 60);
        System.out.println(sec);
        System.out.println(base * 2 * 60 + sec);

    }

    @Test
    public void snakeShapeFillNum() {
        // 蛇形填数：
        int cnt = 2;
        int[][] numberBox = new int[50][50];
        numberBox[0][0] = 1;
        int i = 0;
        int j = 0;
        while (cnt < 1000) {
            j++;
            while (i != -1 && j != -1) {
                numberBox[i][j] = cnt++;
                if (j == 0)
                    break;
                i++;
                j--;
            }
            i++;
            while (i != -1 && j != -1) {
                numberBox[i][j] = cnt++;
                if (i == 0) {
                    break;
                }
                i--;
                j++;
            }
        }
        for (int k = 0; k < 20; k++) {
            for (int l = 0; l < 20; l++) {
                System.out.print(numberBox[k][l] + "\t");
            }
            System.out.println();
        }
        System.out.println(numberBox[19][19]);
    }

    @Test
    public void logCount() {
        // 日志统计：统计n行日志中在d时间段内获赞不少于k次的id，并按id从小到大排序输出
        // 日志格式：时间  id
        Random random = new Random();
        int n = random.nextInt(10) + 90;  // 日志行数
        int d = random.nextInt(300) + 300;  // 时间区间大小
        int k = random.nextInt(5) + 10;  // 获赞数，即统计条数
        System.out.printf("n=%S d=%s k=%s \n", n, d, k);
        Log[] logs = new Log[n];
        int[] idCount = new int[5];
        boolean[] results = new boolean[5];
        for (int i = 0; i < n; i++) {
            Log log = new Log();
            log.time = random.nextInt(1000);
            log.id = random.nextInt(5);
            logs[i] = log;
        }
        Arrays.sort(logs, Comparator.comparingInt(log -> log.time));
        for (int i = 0; i < logs.length; i++) {
            System.out.printf("n=%s time=%s id=%s \n", i, logs[i].time, logs[i].id);
        }
        for (int i = 0; i < n; i++) {
            if (results[i]) {
                continue;
            }
            idCount[logs[i].id] = 1;
            int j = i + 1;
            while (j < logs.length) {
                if (logs[j].id == logs[i].id && logs[j].time - logs[i].time < d) {
                    idCount[logs[i].id]++;
                }
                j++;
            }
            if (idCount[logs[i].id] >= k) {
                results[logs[i].id] = true;
            }
        }
        for (int i = 0; i < results.length; i++) {
            if (results[i]) {
                System.out.println(i);
            }
        }
    }

    @Test
    public void monday() {
        // 星期一：注意1901-01-01是星期二
        // 整个20世纪（1901年1月1日至2000年12月31日之间），一共有多少个星期一？(不要告诉我你不知道今天是星期几)
        int year;
        int day;
        int sumday = 0;
        int count = 0;
        for (year = 1901; year <= 2000; year++) {
            if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
                sumday += 366;
            } else {
                sumday += 365;
            }
        }
        for (day = 2; day <= sumday; day += 7) {
            count++;
        }
        System.out.printf("%d", count);
    }

    @Test
    public void mixedDetection() {
        // 混合检测：
        // 新冠病毒混检，假设1%感染率，k个人检测需要k+1盒试剂，试问k取多少最省试剂盒。
        double m = 60000;
        double min = 9999999;
        double k, sum, ans = 0;
        for (k = 1; k <= 100; k++) {
//            sum = (m - k) / k + 0.01 * m * k + 1; // m/k + 0.01*m*k
            sum = m / k + 0.01 * m * k + 1 + 0.01 * (m % k);
            if (sum < min) {
                min = sum;
                ans = k;
            }
        }
        System.out.printf("%s \n", ans);
    }

    @Test
    public void fourNumSumOfSquare() {
        // 四平方和：允许0和1，允许重复
        // 四平方和定理，又称为拉格朗日定理，每个正整数都可以表示为至多4个正整数的平方和。
        // 如果把0包括进去，就正好可以表示为4个数的平方和。比如：
        // 5 = 0^ 2 + 0^ 2 + 1^ 2 + 2^2
        // 7 = 1^ 2 + 1^ 2 + 1^ 2 + 2^2
        Random random = new Random();
        int input = random.nextInt(99999999);
    }

    @Test
    public void guessLetter() {
        // 猜字母：本质上是计算数组下标
        // 把abcd...s共19个字母组成的序列重复拼接106次，得到长度为2014的串。
        // 接下来删除第1个字母（即开头的字母a），以及第3个，第5个等所有奇数位置的字母。
        // 得到的新串再进行删除奇数位置字母的动作。如此下去，最后只剩下一个字母，请写出该字母。
        String str = "abcdefghijklmnopqrs";
        StringBuilder target = new StringBuilder();
        for (int i = 0; i < 106; i++) {
            target.append(str);
        }
        String targetStr = target.toString();
        while (targetStr.length() > 1) {
            int index = 0;
            StringBuilder sb = new StringBuilder(targetStr);
            while (index < targetStr.length()) {
                sb.replace(index, index + 1, " ");
                index += 2;
            }
            targetStr = sb.toString().replaceAll(" ", "");
            System.out.println(targetStr);
        }
        System.out.println(targetStr);
    }

    @Test
    public void timesDiff() {
        // 次数差
        // x星球有26只球队，分别用 a ~ z 的26个字母代表。他们总是不停地比赛。
        // 在某一赛段，哪个球队获胜了，就记录下代表它的字母，这样就形成一个长长的串。
        // 国王总是询问：获胜次数最多的和获胜次数最少的有多大差距？（当然，他不关心那些一次也没获胜的，认为他们在怠工罢了）
        String team = "abcdefghigklmnopqrstuvwxyz";
        int[] winCount = new int[26];
        Random random = new Random();
        StringBuilder inputStr = new StringBuilder();
        for (int i = 0; i < 1000; i++) {
            inputStr.append(team.charAt(random.nextInt(26)));
        }
        System.out.println(inputStr.toString());
        for (int i = 0; i < inputStr.length(); i++) {
            winCount[team.indexOf(inputStr.charAt(i))]++;
        }
        Arrays.sort(winCount);
        int min = 0;
        for (int i = 0; i < winCount.length; i++) {
            if (winCount[i] != 0) {
                min = winCount[i];
                break;
            }
        }
        System.out.println("distance=" + (winCount[winCount.length - 1] - min));
    }

    private String customAddDays(int year, int month, int dayOfMonth, int addDays) {
        int toYear;
        if (addDays >= 365) {
            // 以下两步是假设每年都是365天
            toYear = year + addDays / 365;
            addDays = addDays % 365;
            if (month == Calendar.FEBRUARY && dayOfMonth == 29) {  // 避开2月29号
                addDays++;
                dayOfMonth--;
            }
            int realDiffDays = getEpoDays(toYear, month, dayOfMonth) - getEpoDays(year, month, dayOfMonth);
            // 前面按整年365减的，如果实际跨度大于之前已经减去的部分，应该继续减去少减的天数
            addDays -= realDiffDays - 365 * (toYear - year);
            return customAddDays(toYear, month, dayOfMonth, addDays);
        } else {
            while (true) {
                // 以下是循环累加/减，以趋近正确的月份并最终计算到具体的日期
                if (addDays > 0) {
                    if (addDays <= COMMON_MONTH_DAY[month] - dayOfMonth) { // 月内
                        dayOfMonth += addDays;
                        addDays = 0;
                    } else { // 月外
                        addDays -= (month == Calendar.FEBRUARY && isBigYear(year) ? 29 : COMMON_MONTH_DAY[month]) - dayOfMonth + 1;
                        if (month < Calendar.DECEMBER) { // 未跨年
                            month++;
                        } else {  // 跨年
                            month = Calendar.JANUARY;
                            year++;
                        }
                        dayOfMonth = 1;
                    }
                } else if (addDays < 0) {
                    if (-addDays > dayOfMonth - 1) { // 月外
                        if (month > Calendar.JANUARY) { // 未跨年
                            month--;
                        } else { // 跨年
                            month = Calendar.DECEMBER;
                            year--;
                        }
                        addDays += dayOfMonth;
                        dayOfMonth = isBigYear(year) && month == Calendar.FEBRUARY ? 29 : COMMON_MONTH_DAY[month];
                    } else {  // 月内
                        dayOfMonth += addDays;
                        addDays = 0;
                    }
                } else {
                    break;
                }
            }
            return year + "-" + month + "-" + dayOfMonth;
        }
    }

    /**
     * 获取标准日
     *
     * @param year  年份(正整数)
     * @param month 月份(0~11)
     * @param day   日(月的实际日期，比如28号)
     * @return
     */
    private int getEpoDays(int year, int month, int day) {
        // 正常天数减去闰年天数：逢4、400加1天
        int total = (year - 1) * 365;
        total += ((year - 1) / 4);
        total -= (year - 1) / 100;
        total += (year - 1) / 400;
        for (int i = 0; i < COMMON_MONTH_DAY.length; i++) {
            if (i < month) {
                total += COMMON_MONTH_DAY[i];
            } else {
                break;
            }
        }
        total += day;
        if (month > Calendar.FEBRUARY && isBigYear(year)) {
            total++;
        }
        return total;
    }

    private boolean isBigYear(int year) {
        if (year % 4 == 0 && year % 100 != 0) {
            return true;
        }
        if (year % 400 == 0) {
            return true;
        }
        return false;
    }

    private String getRealNumberStr(int input, int baseLen) {
        System.out.println("input:" + input);
        String simple = "00000000";
        if (baseLen > simple.length()) {
            throw new RuntimeException("最大base长度超长");
        }
        String inputStr = input + "";
        if (inputStr.length() < baseLen) {
            inputStr = simple.concat(inputStr).substring(inputStr.length() + simple.length() - baseLen);
        }
        return inputStr;
    }

    private int calcRIndex(List<Integer> current, int rIndex) {
        if (current.get(rIndex) < 3) {
            current.set(rIndex, current.get(rIndex) + 1);
            if (rIndex != current.size() - 1) {
                rIndex = current.size() - 1;
            }
        } else {
            // 升位或扩容
            if (rIndex == 0) {
                // 扩容
                current.set(0, 1);
                current.add(0);
                rIndex = current.size() - 1;
            } else {
                // 升位
                for (int i = rIndex; i < current.size(); i++) {
                    current.set(i, 0); // 复零
                }
                rIndex--;
                return calcRIndex(current, rIndex);
            }
        }
        return rIndex;
    }

    private String getCurrentStr(List<Integer> current, String[] eleArray) {
//        System.out.print("current={");
        StringBuilder curStr = new StringBuilder("");
        for (int i = 0; i < current.size(); i++) {
//            System.out.print(current.get(i) + ", ");
            curStr.append(eleArray[current.get(i)]);
        }
//        System.out.println("}");
//        System.out.println(curStr.toString());
        return curStr.toString();
    }

    private class Student {
        private String xm;  // 姓名
        private int xh; // 学号
        private double yy;  // 英语
        private double sx;  // 数学
        private double cpp;  // c++
    }

    private class Log {
        private int time;  // 时间
        private int id;  // id
    }
}
